README.md

1365. How Many Numbers Are Smaller Than the Current Number

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != iandnums[j] < nums[i].

Return the answer in an array.

Example 1:

Input: nums = [8,1,2,2,3] Output: [4,0,1,1,3] Explanation: For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). For nums[1]=1 does not exist any smaller number than it. For nums[2]=2 there exist one smaller number than it (1). For nums[3]=2 there exist one smaller number than it (1). For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2). 

Example 2:

Input: nums = [6,5,4,8] Output: [2,1,0,3] 

Example 3:

Input: nums = [7,7,7,7] Output: [0,0,0,0] 

Constraints:

• 2 <= nums.length <= 500
• 0 <= nums[i] <= 100

Solutions (JavaScript)

1. Brute Force

/** * @param {number[]} nums * @return {number[]} */varsmallerNumbersThanCurrent=function(nums){letret=[];for(leti=0,cnt=0;i<nums.length;i++,cnt=0){for(letj=0;j<nums.length;j++){if(nums[j]<nums[i]){cnt++;}}ret.push(cnt);}returnret;};

2. Sort

/** * @param {number[]} nums * @return {number[]} */varsmallerNumbersThanCurrent=function(nums){constsorted=nums.slice().sort((a,b)=>a-b);returnnums.map(num=>sorted.indexOf(num));};

3. Prefix Sum

/** * @param {number[]} nums * @return {number[]} */varsmallerNumbersThanCurrent=function(nums){letprefix=newArray(101).fill(0);nums.forEach(num=>prefix[num]++);for(leti=1;i<101;i++){prefix[i]+=prefix[i-1];}returnnums.map(num=>num>0 ? prefix[num-1] : 0);};